# -*- coding: utf-8 -*-
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt

def create_graph(verbose=True):
    # create a graph, with weight equals to distance
    G = nx.Graph()
    nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K',\
                'L', 'M', 'N', 'P']
    G.add_nodes_from(nodes)

    edges = [('A', 'B', {'weight': 11.1}), \
            ('A', 'D', {'weight': 11.4}), \
            ('A', 'M', {'weight': 8.2}), \
            ('B', 'C', {'weight': 8.2}), \
            ('B', 'D', {'weight': 12.8}), \
            
            ('C', 'D', {'weight': 7.7}), \
            ('C', 'E', {'weight': 11.1}), \
            ('C', 'F', {'weight': 9.4}), \
            
            ('D', 'F', {'weight': 6.9}), \
            ('D', 'J', {'weight': 12.7}), \
            ('D', 'M', {'weight': 14.3}), \
            ('D', 'N', {'weight': 10.0}), \
            ('D', 'P', {'weight': 8.5}), \

            ('E', 'F', {'weight': 7.4}), \
            ('F', 'N', {'weight': 11.2}), \
            
            ('G', 'J', {'weight': 12.9}), \
            ('G', 'K', {'weight': 13.4}), \
            ('G', 'L', {'weight': 14.5}), \
            ('G', 'N', {'weight': 10.6}), \

            ('H', 'I', {'weight': 9.0}), \
            ('H', 'L', {'weight': 12.3}), \

            ('J', 'K', {'weight': 9.5}), \
            ('J', 'M', {'weight': 9.6}), \
            ('J', 'N', {'weight': 6.9}), \
            ('J', 'P', {'weight': 4.2}), \

            ('K', 'L', {'weight': 4.4}), \
            ('K', 'M', {'weight': 15.0}), \
            
            ('N', 'P', {'weight': 5.9})]
    # 创建节点连线的权重
    G.add_edges_from(edges)
    # 画出网络图：
    if verbose:
        nx.draw(G, with_labels=True, font_weight='bold')   
        plt.show() 
    return G, nodes


def return_hotspot(G, path, nodes, nodes_site=[]):
    situation = pd.read_excel(path, index_col=0)
    
    # 根据人口密度计算每一个节点的权重。
    x = {}
    for node in nodes:
        data = situation.loc[node]
        pop_to_area = data['人口（万人）']/data['面积（km2）']
        x[node] = pop_to_area
    s = float(sum(x.values()))
    # 将节点的权重标准化，使得其和为 1.
    nstart = dict((k, v / s) for k, v in x.items())
    if nodes_site:
        print('节点 ',nodes_site,'设置了消防站')
        # 若有节点设置了消防站
        for node in nodes_site:
            nstart[node] = 0*nstart[node]

    else:
        print('没设消防站')
    
    # 使用 PageRank 算法找出重要节点
    x = pagerank(G, nstart, nodes)
    # 根据节点权重进行排序
    x = list(sorted(x.items(), key=lambda x:x[1], reverse=True))
    print('最重要节点是： ', x[0][0], '应在这里设置消防站')
    print('之后是： ', x[1][0])
    print('再后是： ', x[2][0])
    return x[0][0]

def pagerank(G, nstart, nodes, alpha=0.85, personalization=None,
             max_iter=100, tol=1.0e-6, weight='weight',
             dangling=None):
    """
    使用 PageRank 算法计算图中的重点地点。
    G : 图（networkx）
  
    alpha : 下滑系数。
  
    max_iter : 最大迭代次数，（防止无法收敛）
  
    tol : 容差，判断收敛的依据
    nstart : 初始化每个节点的权重

  
    dangling: dict, optional
      The outedges to be assigned to any "dangling" nodes, i.e., nodes without
      any outedges. The dict key is the node the outedge points to and the dict
      value is the weight of that outedge. By default, dangling nodes are given
      outedges according to the personalization vector (uniform if not
      specified). This must be selected to result in an irreducible transition
      matrix (see notes under google_matrix). It may be common to have the
      dangling dict to be the same as the personalization dict.
  
    Returns
    -------
    pagerank : dictionary
       Dictionary of nodes with PageRank as value
  
    Notes
    -----
    The eigenvector calculation is done by the power iteration method
    and has no guarantee of convergence.  The iteration will stop
    after max_iter iterations or an error tolerance of
    number_of_nodes(G)*tol has been reached.
  
    The PageRank algorithm was designed for directed graphs but this
    algorithm does not check if the input graph is directed and will
    execute on undirected graphs by converting each edge in the
    directed graph to two edges.
  
      
    """
    if len(G) == 0:
        return {}
  
    if not G.is_directed():
        D = G.to_directed()
    else:
        D = G
    
    x = nstart
    
    # 将每一个节点的链接权重标准化，使其和为 1。
    W = nx.stochastic_graph(D, weight='weight')

    N = W.number_of_nodes()
  
    # power iteration: make up to max_iter iterations
    for _ in range(max_iter):
        xlast = x
        x = dict.fromkeys(xlast.keys(), 0)
        for n in x:
  
            # this matrix multiply looks odd because it is
            # doing a left multiply x^T=xlast^T*W
            for nbr in W[n]:
                x[nbr] += alpha * xlast[n] * W[n][nbr]['weight']
  
        # check convergence, l1 norm
        err = sum([abs(x[n] - xlast[n]) for n in x])
        if err < N*tol:
            return x
    raise NetworkXError('pagerank: power iteration failed to converge '
                        'in %d iterations.' % max_iter)
if __name__ == '__main__':
    path = r'../附件/附件1：各区域的人口、面积.xlsx'
    G, nodes = create_graph(verbose=False)
    
    # 没有消防站时
    return_hotspot(G, path, nodes)
    # 有消防站时
    return_hotspot(G, path, nodes, nodes_site=['J', 'N'])
    
    sites = ['J', 'N']
    x = return_hotspot(G, path, nodes, nodes_site=['J', 'N'])
    for _ in range(3):
        sites.append(x)
        x = return_hotspot(G, path, nodes, nodes_site=sites)
        
